应用C++栈实现简单计算器  
2014-10-24 11:28:04|  分类： 默认分类 |  标签：数据结构   

摘要：
本计算器基本基本可以实现“+、-、*、/、^”五种运算，可以判断括号（仅限于”(”和”)”）是否匹配
一、实验构思：
本实验分先分三个部分进
1、先进行括号匹配
2、任何进行中缀表达式转后缀表示式
3、最后缀表达式计算
最后把上述3条程序有机拼接改装成面向对象的Calculator程序
二、实验设计：
1、括号匹配
基本算法思想


 定义一个空栈，读入字符至字符串尾。如果字符是“（”，则将其压入栈中。如果字符是“）”，那么若栈为空，则输出“error”;若栈不为空，则将栈顶元素弹出。当读到最后一个字符时，如果栈尾空，则输出“error”。
 
测试程序
#include<iostream>
#include<stack>
#include<string>
#include<cctype>
#include<cmath>
using namespace std;
void main(){
	string s;
	cin>>s;
	stack<char> S;
	bool judge=1;
	int l=s.length();
	int k=0;
	for(int i=0;i<l;i++){
		if(s[i]=='('){
			S.push(s[i]);
			k++;
		}
		else if(s[i]==')'){
			if(S.empty())
				judge=0;
			else{
				char str=S.top();
				S.pop();
			}
		}
		if(i==l-1&&S.empty()==0)
			judge=0;
	}
	if(judge)
		cout<<"ture"<<endl;
	else
		cout<<"error"<<endl;
 
}
2、中缀转后缀表达式
 
基本算法思想
  中缀表达式转后缀表达式遵循以下原则：
1.遇到操作数，直接输出；（在每个完整的数后面添加一个空格进行分割，便于后面的后缀表达式计算）
2.栈为空时，遇到运算符，入栈；
3.遇到左括号，将其入栈；
4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，
左括号不输出；
5.遇到其他运算符“+、-、*、/、^”时，弹出所有优先级大于或等于该运算符的栈顶
元素，然后将该运算符入栈；
6.最终将栈中的元素依次出栈，输出。
 
测试程序
#include<iostream>
#include<cctype>
#include<stack>
#include<queue>
#include<string>
using namespace std;
int iny(char a){
	switch(a){
		case '#':
			return 0;break;
		case '(':
			return 1;break;
		case '+':
			return 3;break;
		case '-':
			return 3;break;
		case '*':
			return 5;break;
		case '/':
			return 5;break;
	}
}
int outy(char a){
	switch(a){
		case '+':
			return 2;break;
		case '-':
			return 2;break;
		case '*':
			return 4;break;
		case '/':
			return 4;break;
		case '(':
			return 6;break;
		case ')':
			return 1;break;
	}
}
void main(){
	string s;
	cin>>s;
	stack<char> S;char t='#';
	S.push(t);
	string c;
	int l=s.length();
	for(int i=0;i<l;i++){
		if(isdigit(s[i]))
			c=c+s[i];
		else{
			if(iny(S.top())<outy(s[i]))
				S.push(s[i]);
			else{
				while(iny(S.top())>outy(s[i])){
					c=c+S.top();
					S.pop();
				}
				if(iny(S.top())==outy(s[i]))
					S.pop();
				else
					S.push(s[i]);
			}		
		}
	}
	while(S.top()!='#'){
			c=c+S.top();
			S.pop();
	}
	cout<<c<<endl;	
}
 
3、后缀表达式计算
设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的 放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。
 
测试程序
#include<iostream>
#include<stack>
#include<string>
#include<cctype>
#include<sstream>
using namespace std;
inline double str2num(const string &str){
	istringstream stream(str);
	double result;
	stream>>result;
	return result;
}
void main(){
	string s;
	getline(cin,s);
	stack<double> m;
	double c=s.length();
	double a,b;string num,cl;
	for(int i=0;i<c;i++){
		if(isdigit(s[i])||s[i]=='.')
			num=num+s[i];
		else if(s[i]==' '){
				m.push(str2num(num));
				num=cl;
			}
		else{
			b=m.top();m.pop();
			a=m.top();m.pop();
			switch(s[i]){
				case '+':
					m.push(a+b);break;
				case '-':
					m.push(a-b);break;
				case '*':
					m.push(a*b);break;
				case '/':
					m.push(a/b);break;
 
			}
		}
		
	}
	double su=m.top();
	cout<<su<<endl;
 
}
三、实验成果
最后把上述3条程序有机拼接改装成面向对象的Calculator程序
/*Calculator.h*/
#ifndef CALCULATOR_H
#define CALCULATOR_H
#include<string>
using namespace std;
class calc{
private:
	string s;
	bool pipei();
	int iny(char a);
	int outy(char a);
	string zhuan();
public:
	void run();	
};
#endif
/*Calculator.cpp*/
#include"Calculator.h"
#include<iostream>
#include<stack>
#include<string>
#include<cctype>
#include<cmath>
#include<sstream>
using namespace std;
inline double str2num(const string &str){	//字符串转换成实数的函数
	istringstream stream(str);
	double result;
	stream>>result;
	return result;
}
bool calc::pipei(){
	stack<char> S;
	bool judge=1;
	int l=s.length();
	int k=0;
	for(int i=0;i<l;i++){
		if(s[i]=='('){
			S.push(s[i]);
			k++;
		}
		else if(s[i]==')'){
			if(S.empty())
				judge=0;
			else{
				char str=S.top();
				S.pop();
			}
		}
		if(i==l-1&&S.empty()==0)
			judge=0;
	}
	if(judge){
		cout<<"ture"<<endl;return judge;
	}
	else{
		cout<<"error"<<endl;return judge;
	}
}
int calc::iny(char a){                //栈内操作符的优先级
	switch(a){
		case '#':
			return 0;break;
		case '(':
			return 1;break;
		case '+':
			return 3;break;
		case '-':
			return 3;break;
		case '*':
			return 5;break;
		case '/':
			return 5;break;
		case '^':
			return 7;break;
	}
}
int calc::outy(char a){							//栈外操作符的优先级
	switch(a){
		case '+':
			return 2;break;
		case '-':
			return 2;break;
		case '*':
			return 4;break;
		case '/':
			return 4;break;
		case '^':
			return 6;break;
		case '(':
			return 8;break;
		case ')':
			return 1;break;
	}
}
string calc::zhuan(){						//中缀表达式转后缀表达式
	stack<char> S;char t='#';
	S.push(t);
	string c;bool o=0;
	int l=s.length();
	for(int i=0;i<l;i++){
		if(isdigit(s[i])||s[i]=='.'){
			c=c+s[i];o=1;
			if(i==l-1)
				c=c+' ';
		}
		else{
			if(o==1){
				c=c+' ';
				o=0;
			}
			if(iny(S.top())<outy(s[i]))
				S.push(s[i]);
			else{
				while(iny(S.top())>outy(s[i])){
					c=c+S.top();
					S.pop();
				}
				if(iny(S.top())==outy(s[i]))
					S.pop();
				else
					S.push(s[i]);
			}		
		}
	}
	while(S.top()!='#'){
			c=c+S.top();
			S.pop();
	}
	return c;	
}
void calc::run(){
	cin>>s;
	if(pipei()){
		s=zhuan();
		cout<<s<<endl;		//输出后缀表达式每个实数后有一个空格作为分割
		stack<double> m;
		int c=s.length();
		double a,b;string num,cl;
		for(int i=0;i<c;i++){
			if(isdigit(s[i])||s[i]=='.')
				num=num+s[i];
			else if(s[i]==' '){
					m.push(str2num(num));
					num=cl;
				}
			else{
				b=m.top();m.pop();
				a=m.top();m.pop();
				switch(s[i]){
					case '+':
						m.push(a+b);break;
					case '-':
						m.push(a-b);break;
					case '*':
						m.push(a*b);break;
					case '/':
						m.push(a/b);break;
					case '^':
						m.push(pow(a,b));break;
				}
			}
			
		}
		double su=m.top();
		cout<<su<<endl;
	}
	else{
		cout<<"括号不匹配无法进行计算"<<endl;
	}
}
/*Calculator1.cpp*/
#include"Calculator.h"
void main(){
	calc a;
	a.run();
}
四、实验例子

 

五、实验不足
本计算器只可以计算5种基本的运算，而且无法计算高精度计算，只能计算double精度下的运算，而且无法解决精度溢出的问题